This invention relates to a method and apparatus of merging and, particularly, to a method and apparatus of merging suitable for multiple-way merging.
The merging process is defined to be rearrangement of a plurality of data strings, each arranged under a same law, into a single data string in compliance with the same law. An example of merging process is to re-arrange a plurality of numeric strings each arranged in the ascending order of numerals to a numeric string in the ascending order of numerals. Other merging processes include re-arrangement of character strings each in the alphabetic order to a character string in the alphabetic order. An application of merging process is seen in the commercial process, in which the quantities of commodities sold in a day are listed in the order of commodity number at the end of the day.
There has been known a vector merging processor which is capable of performing two-way merging, for example, in which two input data strings are merged through the provision of working areas in the main storage including two areas each for storing one of the input data strings and an area with a capacity of two input data strings for storing the result of merging. This processor, however, necessitates working areas which are twice the volume of two input data strings, and therefore it is not suitable for merging mass data. The above-mentioned vector merging process signifies merging a plurality of vector data.
A merging technique which resembles the above-mentioned prior art is disclosed in JP-A-60-134973 (corresponding to U.S. Pat. Application Ser. No. 685,116 "Vector Processor"now U.S. Pat. No. 4,779,192). A software-oriented multiple-way merging technique is described in an article entitled "Sorting and Searching", Vol. 3, pp. 251-253, published by Knuth, copyrighted by Addison-Wesley Publishing Co. in 1973, in which the manner of "replacement selection" is used to produce an element of output at one time.